package com.likou.second_challenge;

public class q148 {

    // 归并
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode first = head;
        ListNode second = slow.next;
        slow.next = null;
        ListNode left = sortList(first);
        ListNode right = sortList(second);

        return merag(left, right);
    }

    private ListNode merag(ListNode left, ListNode right) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                p.next = new ListNode(left.val);
                left = left.next;
            } else {
                p.next = new ListNode(right.val);
                right = right.next;
            }

            p = p.next;
        }

        if (left == null) {
            p.next = right;
        } else {
            p.next = left;
        }

        return res.next;
    }
}
